package leetcode8;

public class test46 {
    /**
     * 236. 二叉树的最近公共祖先
     * @param root
     * @param p
     * @param q
     * @return
     */
    //暴力解法
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null)return root;
        if(root.val == p.val || root.val == q.val)return root;
        if(find(root.left,p) && find(root.left,q)){
            return lowestCommonAncestor(root.left,p,q);
        }
        if(find(root.right,p) && find(root.right,q)){
            return lowestCommonAncestor(root.right,p,q);
        }
        return root;
    }
    public boolean find(TreeNode root,TreeNode res){
        if(root == null)return false;
        if(root.val == res.val)
            return true;
        return find(root.left,res) || find(root.right,res);
    }

    //递归完美解法
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left == null && right == null) return null; // 1.
        if(left == null) return right; // 3.
        if(right == null) return left; // 4.
        return root; // 2. if(left != null and right != null)
    }
}
